//
// Created by Yandel on 2024/11/28.
//
/**
* 线索二叉树  考研仅需了解即可！
*/
#include <stdio.h>
#include <stdlib.h>

// 定义线索二叉树节点结构
typedef struct ThreadedTreeNode {
    int value;                  // 节点的值
    struct ThreadedTreeNode *left;  // 左子节点指针
    struct ThreadedTreeNode *right; // 右子节点指针
    int leftThread;             // 左指针是否为线索，1 为线索，0 为指向左子节点
    int rightThread;            // 右指针是否为线索，1 为线索，0 为指向右子节点
} ThreadedTreeNode;

// 创建一个新的线索二叉树节点
ThreadedTreeNode* createNode(int value) {
    ThreadedTreeNode *node = (ThreadedTreeNode *)malloc(sizeof(ThreadedTreeNode));
    node->value = value;
    node->left = node->right = NULL;
    node->leftThread = node->rightThread = 0;  // 初始化为子节点指针
    return node;
}

// 线索二叉树的中序线索化
void threadInOrder(ThreadedTreeNode *root, ThreadedTreeNode **pre) {
    if (root == NULL) return;

    // 递归遍历左子树
    threadInOrder(root->left, pre);

    // 处理当前节点
    if (root->left == NULL) {
        root->left = *pre;  // 将当前节点的左指针指向前驱节点
        root->leftThread = 1;  // 标记为线索
    }

    if (*pre != NULL && (*pre)->right == NULL) {
        (*pre)->right = root;  // 将前驱节点的右指针指向当前节点
        (*pre)->rightThread = 1; // 标记为线索
    }

    *pre = root;  // 更新前驱节点为当前节点

    // 递归遍历右子树
    threadInOrder(root->right, pre);
}

// 中序遍历线索二叉树
void inOrderTraversal(ThreadedTreeNode *root) {
    ThreadedTreeNode *current = root;

    // 找到中序遍历的第一个节点（最左节点）
    while (current != NULL && current->leftThread == 0) {
        current = current->left;
    }

    // 中序遍历
    while (current != NULL) {
        printf("%d ", current->value);

        // 如果当前节点的右指针是线索，直接跳到后继节点
        if (current->rightThread == 1) {
            current = current->right;
        } else {
            // 否则，移动到右子树并继续遍历
            current = current->right;
            while (current != NULL && current->leftThread == 0) {
                current = current->left;
            }
        }
    }
}

// 创建线索二叉树并进行中序线索化
ThreadedTreeNode* createThreadedBinaryTree() {
    // 创建节点
    ThreadedTreeNode *root = createNode(1);
    ThreadedTreeNode *node2 = createNode(2);
    ThreadedTreeNode *node3 = createNode(3);
    ThreadedTreeNode *node4 = createNode(4);
    ThreadedTreeNode *node5 = createNode(5);
    ThreadedTreeNode *node6 = createNode(6);
    ThreadedTreeNode *node7 = createNode(7);

    // 建立树结构
    root->left = node2;
    root->right = node3;
    node2->left = node4;
    node2->right = node5;
    node3->left = node6;
    node3->right = node7;

    // 中序线索化
    ThreadedTreeNode *pre = NULL;
    threadInOrder(root, &pre);

    return root;
}

int main() {
    // 创建并线索化二叉树
    ThreadedTreeNode *root = createThreadedBinaryTree();

    // 中序遍历线索二叉树
    printf("中序遍历线索二叉树: ");
    inOrderTraversal(root);
    printf("\n");

    return 0;
}



